import java.util.HashSet;

/*
 * @lc app=leetcode.cn id=1046 lang=java
 *
 * [1046] 最后一块石头的重量
 */

// @lc code=start
class Solution {
    public int lastStoneWeight1(int[] stones) {
        if(stones.length == 1) return stones[0];
        Arrays.sort(stones);
        int len = stones.length-1;
        for(int i = len ;i>=0 ;i--){
            stones[len] = stones[len] - stones[len-1];
            stones[len-1] = 0;
            Arrays.sort(stones);
        }
        return stones[len];
    }

    //用大根堆的方法，堆顶就是最大值，但是这个效率还低一点
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);//lamda表达式
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }

}
// @lc code=end

